\documentclass[main]{subfiles} 

\begin{document}
	\section{dijkstra复习【20250120】}
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P3371}{洛谷-P3371}}
	Dijkstra模板题，数据较弱。
	
	\hypertarget{洛谷-P4779}{}
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P4779}{洛谷-P4779}}
	Dijkstra模板题，数据较强。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1772}{洛谷-P1772}}
	$cost_{i,j}$表示在$[i,j]$天，只能使用一条运输路线时的最小成本，$cost_{i,j}$可以通过删点跑Dijkstra求出。$f_{i,j}$表示总共使用了$i$种不同的运输路线，跑完前$j$天的最小成本。
	
	\[ 
	f_{i,j}=\begin{cases}
		min\{f_{i-1,p}+cost_{p+1,j}+k\ |\ 0\leq p<j\}\ &if\ i,j \in [1,n]\\
		0\ &if\ i=0, j=0
	\end{cases}
	\]
	
	因为第一次选择运输路线不需要花费k的成本，所以$$ans=min\{ f_{i,n}-k\ |\ i \in [1,n]\}$$
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-229B\#author=longyuxuan789}{CodeForces-229B}}
	$wait\_time_{i,t}$表示在$t$时刻准备从星球$i$出发需要额外等多久。Dijkstra修改为$dist_v=min\{dist_u+w_{u,v}+wait\_time_{u,dist_u}\ |\ e(u,v) \in E\}$即可。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1915G\#author=DeepSeek\_zh}{CodeForces-1915G}}
	加一维记录当前用的哪辆自行车，用$dist_{u,i}$表示到$u$这个点目前骑着第$i$辆自行车的最短时间，然后跑Dijkstra即可。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-20C\#author=longyuxuan789}{CodeForces-20C}}
	Dijkstra模板题。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1076D\#author=xwd456}{CodeForces-1076D}}
	保留$n-1$条边就能让所有的点的最短路都不变，所以$x=min\{k, n-1\}$。在Dijkstra求出最短路后，从1开始DFS遍历，只走$e(u,v)\ |\ dist_v=dist_u+w_{u,v}$，输出前$x$条边的编号即可。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1846G\#author=DeepSeek\_zh}{CodeForces-1846G}}
	建$2^n$个点表示当前症状，对于状态$u$服用了第$i$种药物$d_i$天后到达了状态$v$，则建一条边$e(u,v)=d_i$。在这个图上跑Dijkstra即可。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-1887B\#author=GPT\_zh}{CodeForces-1887B}}
	Dijkstra修改为$dist_v=min\{cost_{u,v,Type_{u,v},dist_u}\},cost_{u,v,Type_{u,v},dist_u}$表示$Type_{u,v}$类型的这条边$e(u,v)$，从$dist_u$开始最近的能够使用的时刻。
	
	\subsection{\href{https://vjudge.net/problem/CodeForces-95C\#author=DeepSeek\_zh}{CodeForces-95C}}
	新建一个图$G^{'}= \{ V,E^{'} \}$，$e(u,v)=c_u \in E^{'}\ |\ dist_{u,v} \leq t_u$。在$G^{'}$上跑一遍Dijkstra即可。
	
	\hypertarget{洛谷-P1608}{}
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P1608}{洛谷-P1608}}
	在Dijkstra求出最短路后，令$f_i$表示从$i$到$n$最短路条数。
	
	$$
	f_i=\begin{cases}
		\displaystyle\sum_{dist_i=dist_j+w(i,j)}{f_j}&if\ i\neq n\\
		1&if\ i=n,dist_n \neq \infty\\
		0&if\ i=n,dist_n = \infty
	\end{cases}
	$$
	
	一开始写的时候没有注意判掉$dist_n = \infty$的情况，会导致邻接矩阵中的$\infty$被视为一条边；另外重边问题也没有考虑。
	
	\newpage
	\hypertarget{CodeForces-545E}{}
	\subsection{\href{https://vjudge.net/problem/CodeForces-545E\#author=DeepSeek\_zh}{CodeForces-545E}}
	题目要求求一棵生成树，使得起点$Root$到每个点的路径都是原图中的最短路，并且树的边权和最小。
	
	拿到题目的第一想法就是先求$Root$到其他点的最短路，然后对于$G^{'}=(V,E^{'}=\{e(u,v)=w\ |\ dist_v=dist_u+w\})$求最小生成树。最小生成树有两种算法：Kruscal \& Prim，很容易想到对于$G^{'}$这个有向图而言Kruscal会导致$Root$到某个点的路径不是原图中的最短路，因此考虑Prim。但是很遗憾，Prim也是错误的，具体反例见图\ref{fig:Input}和图\ref{fig:ans}。
	\begin{figure}[htbp]
		\centering
		\includegraphics[scale=0.5]{CodeForces-545E/graph.png}
		\caption{输入数据，以4为起点}
		\label{fig:Input}
		\subfigure[]%为每张图单独设置编号
		{
			\begin{minipage}[b]{.2\linewidth}
				\centering
				\includegraphics[scale=0.3]{CodeForces-545E/prim.png}
			\end{minipage}
		}
		\subfigure[]
		{
			\begin{minipage}[b]{.2\linewidth}
				\centering
				\includegraphics[scale=0.3]{CodeForces-545E/ans.png}
			\end{minipage}
		}
		
		\caption{a为使用Prim时的答案，b为正确答案}
		\label{fig:ans}		
	\end{figure}
	
	由于要求$Root$到每个点的路径都是原图中的最短路，所以在答案的生成树中有$dist_u>dist_v\ |\ v\ is\ father\ of\ u\ in\ tree$。所以就有了一个贪心的做法：每次从$V$中选当前剩下的$dist$最小的点$x$加入生成树中，选择的边则是$e_x=min\{e(u,x) \in E^{'}\}$，具体实现的时候可以在做Dijkstra的时候就记录下$e_x$。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P2662}{洛谷-P2662}}
	\href{https://oi.wiki/graph/mod-shortest-path/}{同余最短路}问题。
	
	\subsection{\href{https://vjudge.net/problem/\%E6\%B4\%9B\%E8\%B0\%B7-P8060}{洛谷-P8060}}
	\href{https://oi.wiki/graph/mod-shortest-path/}{同余最短路}问题。	
	
	\subsection{Summary}
	\begin{itemize}
		\item Dijkstra在实现的时候，如果边权为0的边较多的话，$priority\_queue$的$top()$在循环体里面很可能会变，所以$pop()$操作不能写在循环体的最后，如：\hyperlink{洛谷-P4779}{洛谷-P4779}
		\item 
		Dijkstra中如果使用邻接矩阵来存储图的话，要特别注意重边和$\infty$在计算方案的时候会被当做一条边的问题，如\hyperlink{洛谷-P1608}{洛谷-P1608}	
		\item 最小生成树和最短路结合的题目很有意思，容易想叉，需要仔细思考，如\hyperlink{CodeForces-545E}{CodeForces-545E}
	\end{itemize}
\end{document}